# 上台阶问题
## 10节楼梯 每次 1节/2节，求爬上10节楼梯有多少方法
## 思路
'''
先假设需要上 3节楼梯
1 + 1 + 1
1 + 2
2 + 1
三种方法

再假设上4节楼梯，便是基于三节楼梯的基础上多一节楼梯
于是可以 继承三节楼梯的结果，因为三节楼梯的结果再+1就能得到爬上四节楼梯
但是 四节楼梯还存在 2+2的情况，由此可以设想 （4-2）节楼梯的情况
因此可以得到 f(n) = f(n-1) + f(n-2)的计算关系
1 1 1 1
1 2 1
2 1 1
2 2
1 1 2
'''

def f(n):
    # 边界设置
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return 2
    return f(n-1)+f(n-2)

for i in range(10):
    print(f"楼梯有{i}阶的时候，有{f(i)}种走法")

print("="*30)
# 直接循环解决
a = [0,1,2]
for i in range(3,11):
    a.append(a[i-1] + a[i-2])
    print(f"楼梯有{i}阶的时候，有{f(i)}种走法")
